1. Field of the Invention
The invention relates generally to representations of hierarchically organized information and, in particular, to data structures, objects, methods and techniques for matching or, in some realizations, efficiently representing sub-hierarchies thereof.
2. Description of the Related Art
Hierarchically organized data structures are well known in the art and are commonly used in a variety of software implementations and algorithms. In particular, tree-oriented data structures are often used in representations of component/sub-component decompositions of parts or attributes of physical systems. In such applications, successive levels of the tree typically represent additional levels of specialization, resolution or refinement. Tree-oriented data structures are also employed in the representation and/or presentation of information organizations, such as for directory structures, registry information and parse trees.
In general, the particular organization and/or physical encoding employed depend on design constraints or requirements of a particular application. Typically, or at least illustratively, tree-oriented data structures are organized using a hierarchy of nodes, often with associated node information or values and references to other nodes. Other encodings include tagged linear encodings such as using an extensible Markup Language (XML) wherein hierarchies are encoded using nesting. Whatever the particular encoding technique, a node at a higher level in a hierarchy is conventionally known as a parent node and a node (or nodes) at a lower level is (are) known as a child node(s). A highest-level node is often known as a root node and terminal nodes (i.e., nodes that do not themselves refer to other nodes) are known as leaf nodes. Typically, interior nodes have associated node information or values; although some applications of trees or tree-oriented may limit information and values to leaf nodes.
For many applications that employ hierarchically organized data structures, an important class of functionality involves comparison of sub-hierarchies. For example, identification of identical or equivalent subassemblies of parts can be an important function of a product configuration system. In many such applications, product configurations may be appropriately handled as hierarchies of unordered sets. That is to say, for many applications, a subassembly M that consists of components A, B and C is identical (or at least equivalent) to a subassembly M′ that consists of components B, C and A.
Unfortunately, techniques that allow comparison and matching of sub-hierarchies without regard to ordering of elements have generally employed a sorting of elements as a precursor to comparison. In effect, ordering is eliminated as a distinguishing characteristic by ensuring that all orderings of the same elements are themselves the same. Unfortunately, sorting is a computationally expensive operation. For many implementations, a sorting-based solution leads to O(N log2N) scaling. Accordingly, data structures and related techniques are desired whereby improved scaling performance can be achieved while providing efficient matching, comparison or collapsing of hierarchies of arbitrary size and structure without regard to ordering of elements therein.